package main

import "go-leetcode/leetcode/utils"

// 148.排序链表
func main() {
	listNode := utils.GetListNodeByArray([]int{5, 6, 1, 8, 4, 5})

	pointListNode := listNode
	for pointListNode != nil {
		print(pointListNode.Val, " ")
		pointListNode = pointListNode.Next
	}
	println("转换为")

	node := sortList2(listNode)
	pointResNode := node
	for pointResNode != nil {
		print(pointResNode.Val, " ")
		pointResNode = pointResNode.Next
	}
	return
}
func sortList2(head *utils.ListNode) *utils.ListNode {
	// 使用归并排序
	return sortNode(head, nil)
}

func sortNode(head, tail *utils.ListNode) *utils.ListNode {
	if head == nil {
		return head
	}

	if head.Next == tail {
		head.Next = nil
		return head
	}

	slow, fast := head, head
	for fast != tail {
		slow = slow.Next
		fast = fast.Next
		if fast != tail {
			fast = fast.Next
		}
	}

	mid := slow
	return selfMergeTwoLists(sortNode(head, mid), sortNode(mid, tail))
}

func selfMergeTwoLists(list1 *utils.ListNode, list2 *utils.ListNode) *utils.ListNode {
	//if list1 == nil {
	//	return list2
	//}
	//if list2 == nil {
	//	return list1
	//}

	pointHead := &utils.ListNode{}

	pointNode := pointHead

	for list1 != nil || list2 != nil {
		if list1 == nil {
			pointNode.Next = list2
			return pointHead.Next
		}
		if list2 == nil {
			pointNode.Next = list1
			return pointHead.Next
		}

		if list1.Val < list2.Val {
			pointNode.Next = list1
			list1 = list1.Next
		} else {
			pointNode.Next = list2
			list2 = list2.Next
		}
		pointNode = pointNode.Next
	}

	return pointHead.Next
}

func sortList(head *utils.ListNode) *utils.ListNode {
	// 不可，会导致超时
	// 使用冒泡排序，大的放后面，小的放前面，记录整个链表的长度
	// 每次遍历后，最大的就到后面去了

	dummy := &utils.ListNode{
		Val:  -1,
		Next: head,
	}

	var nodeLen int
	lenCount := dummy
	// 先计算链表的长度
	for lenCount.Next != nil {
		nodeLen++
		lenCount = lenCount.Next
	}

	prev := dummy

	for i := nodeLen; i > 1; i-- {
		for j := 1; j < i; j++ {
			if prev.Next.Val > prev.Next.Next.Val {
				// 交换位置
				temp := prev.Next
				prev.Next = prev.Next.Next
				temp.Next = prev.Next.Next
				prev.Next.Next = temp
			}
			prev = prev.Next
		}
		prev = dummy
	}

	return dummy.Next
}

// 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//
//示例 1：
//
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
//示例 2：
//
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
//示例 3：
//
//输入：head = []
//输出：[]
//
//提示：
//
//链表中节点的数目在范围 [0, 5 * 104] 内
//-105 <= Node.val <= 105
//
//进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
